# 72. 编辑距离
# 难度困难
# https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
# 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
# 你可以对一个单词进行如下三种操作：
# 插入一个字符
# 删除一个字符
# 替换一个字符


class EditDistance:

    def minDistance(self, word1: str, word2: str) -> int:
        """一维数组"""
        n = len(word1)
        m = len(word2)
        # dp[i][j]只和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三个量有关，
        # 即二维数组中，当前元素的左边，上边，左上角三个元素。
        # 故用一位数组保存，dp[j]为当前值的左边，相当于dp[i-1][j]
        # dp[j+1]为当前值，相当于dp[i-1][j]
        dp = list(range(m + 1))
        for i in range(n):
            left_up = dp[0]
            dp[0] = i + 1
            for j in range(m):
                dp[j + 1], left_up = min(
                    dp[j] + 1, dp[j + 1] + 1,
                    left_up + int(word1[i] != word2[j])), dp[j + 1]
        return dp[-1]

    def minDistance2(self, word1: str, word2: str) -> int:
        """二维数组"""
        n = len(word1)
        m = len(word2)

        if (n * m == 0):
            return n + m

        # dp数组
        # 用 dp[i][j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离。
        dp = [[0] * (m + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = i
        for i in range(m + 1):
            dp[0][i] = i
        # D[i][j-1] 为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。
        # 即对于 B 的第 j 个字符，我们在 A 的末尾添加了一个相同的字符，那么 D[i][j] 最小可以为 D[i][j-1] + 1；
        # D[i-1][j] 为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。
        # 即对于 A 的第 i 个字符，我们在 B 的末尾添加了一个相同的字符，那么 D[i][j] 最小可以为 D[i-1][j] + 1；
        # D[i-1][j-1] 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。
        # 即对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同，那么 D[i][j] 最小可以为 D[i-1][j-1] + 1。
        # 特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。
        # 在这种情况下，D[i][j] 最小可以为 D[i-1][j-1]。
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                left = dp[i - 1][j] + 1
                down = dp[i][j - 1] + 1
                left_down = dp[i - 1][j - 1]
                if word1[i - 1] != word2[j - 1]:
                    left_down += 1
                dp[i][j] = min(left, down, left_down)
        return dp[n][m]


if __name__ == "__main__":
    print(EditDistance().minDistance("horse", "ros"))
